Введение в язык Scheme для школьников

Часть викиучебника «Лисп»
Исходный вариант статьи (С. И. Иевлев, «Ваш новый язык — Scheme») опубликован в двух частях в журнале «Потенциал».

Вы хорошо знаете русский, возможно, неплохо уже говорите по-английски, в школе вас научили несколько необычному языку математики. Предлагаю выучить ещё один — Лисп. Точнее, один из его самых интересных диалектов — Scheme (Ским).

Введение в синтаксис

Сперва познакомимся с несколько необычным порядком слов этого языка: «действие — предмет». Но необычен он только в сравнении с популярными языками программирования. В русском языке такая последовательность нередка:

Сумма трёх и пяти.
Произведение пяти, шести и семи.
Купить булочный батон.

Каждая законченная фраза на этом языке должна быть окружена парой круглых скобок. Запишем сказанное выше на Scheme:

(+ 3 5)
(* 5 6 7)
(купить булочный батон)

Можно записать выражения и посложнее:

(купить булочная батон (+ 2 1))

«Купи в булочной батоны: два плюс ещё один». Просто, не правда ли? Давайте двигаться дальше. Фраза (* 3 5) хороша, а (* width height) — лучше. Выражение (* 2 3.1415926 5) — интригующе, а (* 2 pi radius) гораздо более осмысленно. Здесь width, height — переменные, а 3 и 5 — их текущие значения.

Переменная задаётся следующей конструкцией языка:

(define имя <первоначальное значение>)

Пример:

(define width 3)
(define height 7)
(* 2 (+ width height))

Прочитаем записанное по-русски: «Положим ширина — это 3, высота — это 7, подсчитаем произведение двух и суммы ширины и высоты (например, периметр прямоугольника)». Результат такого вычисления в нашем случае будет 20.

Продолжим совершенствовать конструкции. Положим, нам требуется подсчитать сумму квадратов двух чисел. Это можно сделать, например, так:

(define a 3)
(define b 4)
(+ (* a a) (* b b))

Что-то не так; мы обычно вместо «помножь переменную на саму себя» говорим «возведи в квадрат эту переменную», на Скиме — square:

(+ (square a) (square b))

«Сумма квадрата a и квадрата b». Есть задача — есть её решение. Мы можем объявить новое слово-функцию, назвать её square. Функция будет принимать в качестве параметра число и возвращать его квадрат. Делается это следующим образом:

(define (square x) (* x x))

Общий формат:

(define (название параметр параметр …) тело_функции)

Функция возвращает последнее вычисленное значение. Это означает, что следующая функция square2:

(define (square2 x) (* 2 2) (* x x))

вернёт тот же результат, что и square, перед этим умножив два на два безо всякого эффекта. Перепишем пример с суммой квадратов чисел заново:

(define a 3)
(define b 4)
(define (square x) (* x x))
(+ (square a) (square b))

Нам не хватало слов в языке — мы их добавили. Вообще, когда пишете программу на Лиспе, вы описываете не алгоритм, а сначала создаёте язык, а потом на нём формулируете исходную задачу. Несколько точнее — вы «подгоняете» данный вам язык Scheme до тех пор, пока он не станет совпадать с языком, на котором задача формулируется легко.

Сразу пример. Пусть перед нами стоит задача сделать программу, которая спрашивает имя пользователя, а потом выводит ему приветствие.

Scheme предоставляет нам несколько готовых «глаголов»:

read: для чтения имени,
display: вывод чего-то на дисплее,
newline: вывод перевода строки.

Мы бы хотели иметь такие «глаголы»:

привет: для приветствия с одним параметром — именем пользователя;
пользователь: для получения имени пользователя, без параметров.

Наша задача выглядела бы так:

(привет (пользователь))

Дело за малым — определить привет и пользователь. Нет проблем. Вот полный текст программы.

(define (привет имя)
  (display "Привет, ")
  (display имя)
  (display "!")
  (newline))
(define (пользователь)
  (write "Представьтесь:")
  (read))
(привет (пользователь))

Лисп — полноценный функциональный язык, а поэтому функции — полноправные члены этого языка, независимо от того, определили вы их сами, или они уже были в языке готовые. В частности, их можно передавать в качестве параметров в другие функции, а там уже делать с ними всё, что потребуется. Например, функцию «модуль числа» можно определить так:

(define (abs x)
  (if (positive? x )
       x
      (- x)))

«Определим, что функция abs возвращает свой аргумент, если он положителен, иначе — -x». А можно и так:

(define (abs x)
  ((if (positive? x) + -) x))

«…если аргумент положителен, то плюс, иначе минус x». Здесь в результате исполнения выражения if возвращается функция + или -, которая затем применяется к аргументу x. Полагаю, что смысл конструкции if вам сразу ясен. Сначала проверяется первый аргумент, если он истинен, то исполняется второй аргумент, иначе третий. Общий формат таков:

(if условие <действие, если условие выполняется> <действие в противном случае>)

Где посмотреть и попробовать

В теории всё хорошо, а где немного попрактиковаться? В мире можно найти много прекрасно разработанных сред для работы со Scheme. К сожалению, большинство документации по Scheme на английском языке, но можно найти и отличные введения на русском — язык-то простой.

Вот названия нескольких самых распространённых реализаций:

Racket: одна из самых полных реализаций, включает в себя удобную обучающую среду Dr.Scheme. Есть версии для платформ Windows, Linux, Mac OS.
Bigloo: тоже достаточно полная реализация. Доступна для платформ Windows, Linux.
LispMe: версия для карманных компьютеров с операционной системой Palm OS.
GNU Guile: распространённая реализация Scheme от проекта GNU, которая используется в ОС GNU Guix. Доступна для GNU/Linux. Возможна компиляция.

Также ещё посмотрите Gambit-C — один из самых быстрых компиляторов Scheme.

Все перечисленные реализации Scheme — это интерпретаторы. Запускаете интерпретатор — и можно вести с ним диалог на Scheme: в ответ на его приглашение вводите конструкции на Scheme, а он будет возвращать результаты вычислений.

Wecome to Mz Scheme version 208, Copyright (c) 2004  PLT Scheme, Inc.
>1
1
>(+ 1 2)
3
>(define a 3)
>(+ a a)
6
>

Попробуйте «проиграть» все вышеперечисленные примеры. Думаю, вам понравится!

Кот в мешке

Простота Scheme обманчива. На самом деле — это один из самых мощных на сегодняшний день языков программирования. На основе этого языка можно изучить все известные стили и методы программирования. С частью этих приёмов мы познакомимся с вами в следующих статьях этой серии.

Упражнение

Посмотрите следующие две реализации функции вычисления факториала $f(n)=1\cdot 2\cdots n$ . Одна из них основана на рекурсии, а другая – на итерациях. Напишите на Scheme рекурсивную и основанную на итерациях реализации функции возведения в степень $f(a,n)=a^{n}$ .

Вариант 1

(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))

Вариант 2

(define (fact-iter result counter)
(if (= counter 0)
    result
    (fact-iter (* counter result)
               (- counter 1))))
(define (factorial n) (fact-iter 1 n))

Повторение – мать учения

Приведём небольшую шпаргалку по базовым конструкциям Scheme для тех, кто еще не ознакомился с первой частью статьи.

Базовый синтаксис:

(<функция> <аргумент> <аргумент> …) ; комментарий

Например:

(+ 1 2 3 4)                     ; сумма первых четырёх натуральных чисел
(+ (+ 1 2) 5 6)                 ; возможно вкладывать одни вызовы функций в другие
(string-append "hello" "world") ; результат — склеенная строка "helloworld"

Задание переменных и функций:

(define <имя> <значение>)
(define (<имя> <аргумент> …) <тело функции>)
; функция возвращает значение последнего вычислительного выражения в теле функции

Например:

(define a 3)
(define b 4)
(define (square x) (* x x)) ; вычисляет квадрат числа
(define (+a x) (+ x a)) ; да-да, можно давать и такие имена функциям

Дополнительные конструкции:

(if <условие> <действие при успехе условия> <действие при неудаче>)
(begin <первое действие> <второе действие> …)

Пример:

(if (> a 0)
     (display "a > 0")) ; действие при неудаче можно не указывать
(begin (display 1)
       (display 2)
       (display 3)) ; последовательно выполнятся действия, и на экран будет выведено: 123

И опять про повторение: функция `repeat`

Ну вот, теперь можно продолжать двигаться дальше. Если вам надо выполнить какое-то действие один раз, то вы просто его делаете один раз:

(display "hello")

Если вам надо выполнить какое-то действие два раза, то вы просто повторяете его:

(display "hello") (display "hello")

А что, если вам нужно повторять работу снова и снова? Тогда мы сделаем функцию, которая будет повторяться требуемое количество раз. Называться эта функция будет repeat, и у неё будет один параметр — количество повторов. Алгоритм следующий:

Если количество повторов больше нуля, то:

выполняем действие
Вызываем функцию repeat с количеством повторов меньшим на 1

(define (repeat number)
       (if (> number 0) ; если количество повторов не нулевое
           (begin (display "hello") ; выполняем действие
                  (repeat (- number 1))))) ; повторим действие на единицу меньшее количество раз.

Попробуем. Запустим один из доступных вам интерпретаторов Scheme, например mzscheme, который можно найти в Интернете по адресу http://www.plt-scheme.org/software/drscheme/ и установить на вашем компьютере.

> (define (repeat number)
                (if (> number 0)
                    (begin (display "hello")
                           (repeat (- number 1)))))
> (repeat 0)
> (repeat 1)
hello
> (repeat 2)
hellohello
> (repeat 3)
hellohellohello

Упражнение 1

Попробуйте написать функцию, которая будет выводить на экран цифру 1 заданное количество раз.

Упражнение 2

Попробуйте написать функцию, которая будет выводить на экран натуральные числа от 1 до заданного числа. Порядок вывода чисел не важен.

Самое время вспомнить, что в Scheme можно передавать функцию в качестве параметра. Усовершенствуем функцию repeat так, чтобы мы смогли повторять произвольные действия заданное количество раз. Пусть новая версия принимает два параметра: первый — количество повторов, второй — функция, которую надо запустить.

(define (repeat number function)
  (if (> number 0)
    (begin (function)
           (repeat (- number 1) function))))

Теперь повторять можно разные действия:

(define (print-one) (display "1"))
(define (print-hello) (display "hello"))
(repeat 3 print-one) ; три раза выведет на экран "1"
(repeat 5 print-hello) ; пять раз выведет на экран "hello"

Принцип наименьших усилий

Не надо делать лишних действий, если их можно избежать. Последний вариант функции repeat хорош, но… зачем каждый раз давать функции имя, если нужно просто её выполнить? А можно ли вообще создать функцию, но не давать ей имя? Оказывается можно. В языке есть специальная инструкция, которая говорит «создать функцию».

(lambda (<аргументы>) <тело функции> <последнее вычисленное значение возвращается>)

Пример:

(lambda (x) (* x x))    ; создать функцию, которая вычисляет квадрат числа
(lambda (x y) (+ x y)) ; создать функцию, которая вычисляет сумму двух чисел
(define square (lambda(x) (* x x)))  ; создать функцию, которая вычисляет квадрат числа и назвать её square.

Оказывается, последняя конструкция то же самое, что и:

(define (square x) (* x x))

Вот мы с вами открыли ещё один способ определять функции с именами: сначала создаём, затем даём имя. Давайте-ка теперь «повторим» действия, не давая имена функциям:

(repeat 3 (lambda() (display "hello")) ) ; три раза выведем на экран "hello"
(repeat 5 (lambda() (display "1"))) ; пять раз выведем на экран "1"

Для repeat используются функции без параметров, поэтому в конструкции lambda пустая пара скобок.

Списки

Проведём следующую работу:

(define a 1)
(define b 2)
(define c 3)
(+ a 1)
(+ b 1)
(+ c 1)

А как бы нам сразу взять три числа и увеличить их на единицу одним махом? Для этого надо «связать» эти числа вместе. Один из способов склеивания — список. Создаётся список следующей конструкцией:

(list <элемент1> <элемент2> <элемент3> …)

Пример:

(define abc (list 1 1 1))                 ; список из трёх единиц
(define lst1 (list 1 2 3))                ; список из трёх разных чисел
(define lst2 (list "hello" "my" "world")) ; список из строк
(define lst3 (list "hello" 1 "world" 3))  ; список из строк и чисел
(define lst4 (list (+ 1 0) 2 3))          ; элементы списка можно вычислять перед его созданием

Scheme также предоставляет функцию:

(map <функция> <список>)

Эта функция возвращает список, в котором каждый элемент есть результат применения <функция> к элементу исходного списка. Пример:

(define (inc x) (+ x 1))  ; увеличивает число на единицу
(map inc (list 1 1 1))    ; возвращает список из двоек
(map square (list 1 2 3)) ; возвращает список из квадратов элементов, то есть 1, 4 и 9

Вспомним про lambda и решим задачу, которую поставили себе в начале этого раздела:

(define abc (list 1 1 1))
(map (lambda(x) (+ x 1)) abc)

А можно даже и список не вводить как дополнительную переменную:

(map (lambda(x) (+ x 1))
       (list 1 1 1))

Упражнение 3

Пользуясь функциями write (для печати списка на экране) и map, напишите функцию, которая будет выводить на экран список, увеличенный на заданное число, например

(print-it 5 (list 1 2 3)) ; выведет "(6 7 8)"

Работа со списками

А как написать функцию, которая последовательно будет перемещаться по заданному списку и выводить каждый элемент этого списка? Для этого нам надо только знать следующие инструкции:

(null? <список>) — проверяет, а есть ли ещё какие элементы в списке,
(car <список>) — возвращает первый элемент списка,
(cdr <список>) — возвращает список из всех элементов, кроме первого, а если больше ничего не осталось, то пустой список.

Пример:

(car (list 1 2 3)) ; вернёт 1
(cdr (list 1 2 3)) ; вернёт список из 2 и 3, то есть (list 2 3).

Проще говоря, функция car возвращает голову списка, а cdr — оставшийся хвост списка.

Имя функции print-list. Единственный параметр — исходный список. Алгоритм работы нашей функции следующий:

Если список не пуст, то:

выводим голову списка.
вызываем print-list для хвоста списка

(define (print-list lst)
(if (not (null? lst))
    (begin (display (car lst))
           (newline)
           (print-list (cdr lst)))))

Поэкспериментируем в интерпретаторе:

> (print-list (list 1 2 3))
1
2
3
> (print-list (list "a"))
a

Упражнение 4

Поэкспериментируйте в интерпретаторе с функциями car, cdr и null?.

Упражнение 5

Напишите функцию, которая будет вычислять длину списка. Длина пустого списка — ноль.

Упражнение 6

Пользуясь изученными функциями car, cdr и null? напишите функцию for-each-element, которая будет применять заданную функцию к каждому элементу данного списка. Например, (for-each-element display (list 1 2 3)) должна напечатать «123». Напишите новую версию print-list, пользуясь только что созданной функцией.

Упражнение 7

Напишите функцию, которая будет принимать на вход два списка и возвращать список из попарных сумм элементов, например, команда (plus (list 1 2) (list 5 6)) должна вернуть список (6 8).

Упражнение 8

Попробуйте решить упражнение 7 с помощью функции map — правильный ответ вас сильно удивит.

См. также

Викиучебник «Лисп».
Лисп, статья в Википедии.
Scheme, статья в Википедии.
Plt Scheme, официальная страница Plt Scheme.
Bigloo, страничка о Bigloo.
LispMe, официальная страница LispMe.
Gambit-C, здесь можно скачать Gambit-C.

Учебники на английском

Teach Yourself Scheme in Fixnum Days , Dorai Sitaram.
The Scheme Programming Language, R. Kent Dybvig.
Schematics Scheme Cookbook.
The Common Lisp Cookbook.
Practical Common Lisp.
Видео лекции "Structure and Interpretation of Computer Programs", Harold Abelson и Gerald Jay Sussman.

Введение в синтаксис

Где посмотреть и попробовать

Кот в мешке

Упражнение

Вариант 1

Вариант 2

Повторение – мать учения

И опять про повторение: функция repeat

Упражнение 1

Упражнение 2

Принцип наименьших усилий

Списки

Упражнение 3

Работа со списками

Упражнение 4

Упражнение 5

Упражнение 6

Упражнение 7

Упражнение 8

См. также

И опять про повторение: функция `repeat`